package com.murphy.algorithm.likou;

/**
 * 二叉树最小的公共祖先节点
 * @author dongsufeng
 * @version 4.0
 * @date 2023/2/23 10:35
 */
public class LowestCommonAncestor {


    public TreeNode common0(TreeNode root,int n1,int n2){
        if (root==null || root.val==n1 || root.val==n2){
            return root;
        }
        TreeNode l =common(root.l,n1,n2);
        TreeNode r = common(root.r,n1,n2);
//        如果左右都不为空说明root就是
        if (l!= null && r!=null){
            return root;
        }
//        如果左边为空说明在右边，反之
        return l==null ? r : l;
    }

    public TreeNode common1(TreeNode root,int n1,int n2){
        if (root==null || root.val==n1 || root.val==n2){
            return root;
        }
        if (n1<root.val && n2<root.val){
            return common1(root.l,n1,n2);
        }
        if (n1>root.val && n2>root.val){
            return common1(root.r,n1,n2);
        }
        return root;
    }

    /**
     * 无序树
     * @param root
     * @param n1
     * @param n2
     * @return
     */
    public TreeNode common2(TreeNode root,int n1,int n2){
        if (root == null || root.val == n1 || root.val == n2){
            return root;
        }
        TreeNode l = common2(root.l,n1,n2);
        TreeNode r = common2(root.r,n1,n2);
        if (l != null && r != null){
            return root;
        }
        return l == null ? r : l;
    }

    /**
     * 有序树
     * @param root
     * @param n1
     * @param n2
     * @return
     */
    public TreeNode common(TreeNode root,int n1,int n2){
       if (root == null || n1 == root.val || n2 == root.val){
           return root;
       }
       if (root.val > n1 && root.val > n2){
           return common(root.l,n1,n2);
       }else if (root.val < n1 && root.val < n2){
           return common(root.r,n1,n2);
       }else {
           return root;
       }
    }


    public static class TreeNode{
        private int val;
        private TreeNode l;
        private TreeNode r;

        public TreeNode(){}

        public TreeNode(int val){
            this.val=val;
        }
    }

    public static void main(String[] args) {
        LowestCommonAncestor lowestCommonAncestor = new LowestCommonAncestor();
        TreeNode treeNode = new TreeNode(5);
        TreeNode treeNode3 = new TreeNode(3);
        treeNode.l=treeNode3;
        TreeNode treeNode2 = new TreeNode(2);
        treeNode.l.l=treeNode2;
        TreeNode treeNode4 = new TreeNode(4);
        treeNode.l.r=treeNode4;

        TreeNode treeNode7 = new TreeNode(7);
        treeNode.r=treeNode7;
        TreeNode treeNode6 = new TreeNode(6);
        treeNode.r.l=treeNode6;
        TreeNode treeNode8 = new TreeNode(8);
        treeNode.r.r=treeNode8;

        TreeNode t =lowestCommonAncestor.common(treeNode,6,8);
        System.out.print(t.l.val);
        System.out.print(t.val);

        System.out.print(t.r.val);
        System.out.println("===========");
        TreeNode t1 =lowestCommonAncestor.common1(treeNode,6,8);
        System.out.print(t1.l.val);
        System.out.print(t1.val);

        System.out.print(t1.r.val);
    }
}
